package alg.sort;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * 单边循环递归快速排序
 * @author xujian
 * 2021-06-29 14:04
 **/
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {10,2,4,2,1,6,8,7,9};
        quickSort2(arr,0,arr.length-1);
        for (int i : arr) {
            System.out.print(i+",");
        }
    }

    /**
     * 递归实现
     * @param arr
     * @param startIndex
     * @param endIndex
     */
    public static void quickSort(int arr[],int startIndex,int endIndex) {
        if (startIndex >= endIndex) {
            return;
        }
        int prov = partition(arr,startIndex,endIndex);
        quickSort(arr,startIndex,prov-1);
        quickSort(arr,prov+1,endIndex);
    }

    /**
     * 非递归实现
     * @param arr
     * @param startIndex
     * @param endIndex
     */
    public static void quickSort2(int arr[],int startIndex,int endIndex) {
        if (startIndex >= endIndex) {
            return;
        }
        Stack<Map<String,Integer>> stack = new Stack<>();
        Map<String,Integer> map = new HashMap<>();
        map.put("startIndex",startIndex);
        map.put("endIndex",endIndex);
        stack.push(map);
        while (!stack.isEmpty()) {
            Map<String,Integer> map1 = stack.pop();
            int prov = partition(arr,map1.get("startIndex"),map1.get("endIndex"));
            if (map1.get("startIndex") < prov-1) {
                Map<String,Integer> map2 = new HashMap<>();
                map2.put("startIndex",map1.get("startIndex"));
                map2.put("endIndex",prov-1);
                stack.push(map2);
            }
            if (map1.get("endIndex") > prov+1) {
                Map<String,Integer> map3 = new HashMap<>();
                map3.put("startIndex",prov+1);
                map3.put("endIndex",map1.get("endIndex"));
                stack.push(map3);
            }
        }
    }

    public static int partition(int arr[],int startIndex,int endIndex) {
        int prov = arr[startIndex];
        int mask = startIndex;
        for (int i = startIndex+1; i <= endIndex ; i++) {
            if (arr[i] < prov) {
                mask++;
                int tmp = arr[mask];
                arr[mask] = arr[i];
                arr[i] = tmp;
            }
        }
        int tmp = arr[mask];
        arr[mask] = prov;
        arr[startIndex] = tmp;
        return mask;
    }
}
